/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    let res = new Array(n+1)
    for(let i = 1; i <= n; i++) {
        if(i == 1){
            res[1] = 1 
            continue
        } 
        if(i == 2) {
            res[2] = 2
            continue
        }
        if(i == 3) {
            res[3] = 3
            continue
        }
        if(Math.sqrt(i)%1==0) {
            res[i] = 1
            continue
        }
        let l = 1, r = i - 1
        let min = res[l] + res[r]
        while(l <= r) {
            if(res[l] + res[r] < min) {
                min = res[l] + res[r]
            }
            l++
            r--
        }
        res[i] = min
    }
    return res[n]
};
console.log(numSquares(13))